'''
难度 简单
标签 链表
题目链接 https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/description/
'''
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random

class Solution:
    # 使用 hash 表
    def copyRandomList1(self, head: 'Node') -> 'Node':
        # 判空
        if not head:
            return head

        # 初始化一个哈希表
        hmap = {}

        curr = head
        # 复制各节点，初始化各节点 并建立 Map 映射
        while curr:
            hmap[curr] = Node(curr.val)
            curr = curr.next
        
        curr = head
        # 构建 next 和 redom 指向
        while curr:
            hmap[curr].next = hmap.get(curr.next)
            hmap[curr].random = hmap.get(curr.random)
            curr = curr.next
        
        # 返回新链表的头节点
        return hmap[head]
    
    # 采用复制各节点及其对应的 next, random 再拆分
    def copyRandomList(self, head: 'Node') -> 'Node':
        # 判空
        if not head:
            return head

        # 复制一个当前的节点 放在当前节点的后面
        curr = head
        while curr:  
            temp = Node(curr.val)
            temp.next = curr.next 
            curr.next = temp
            curr = temp.next
        
        # 处理复制的节点的 random
        curr = head
        while curr:  
            # 防止指向空指针
            if curr.random: 
                # 节点与复制节点的random 也是相隔一个
                curr.next.random = curr.random.next
            # 循环跳过复制的节点
            curr = curr.next.next
        
        # 拆分两个链表
        pre = head
        curr = res = head.next
        while curr.next:
            pre.next = pre.next.next
            curr.next = curr.next.next
            pre = pre.next
            curr = curr.next
        
        # 复制链表最后一个为空 原链表最后一个元素需要手动置空
        pre.next = None

        return res
    

if __name__ == '__main__':
    s = Solution()
    参数 = [
        [[4,5,1,9], 5],
        [[4,5,1,9], 1],
    ]
    预期 = [
        [4,1,9],
        [4,5,9],
    ]
    for k,v in enumerate(参数):
        r = s.getIntersectionNode(v[0])
        if r != 预期[k]:
            print("第{}个case不通过 期望={} 结果={}\n".format(
                k+1,
                预期[k],
                r
            ))